package com.leetcode.algorithm.y19.m04;

import com.leetcode.algorithm.common.ListNode;

/**
 * leetcode-cn.com
 * 
 * (done)21. 合并两个有序链表
 * (done)2. 两数相加
 * (done)61. 旋转链表
 * @author: jie.deng
 * @time: 2019年4月16日 上午12:18:44
 */
public class MySolution0414 {
    
    /**
     * 21. 合并两个有序链表 
     * 将两个有序链表合并为一个新的有序链表并返回。
     * 新链表是通过拼接给定的两个链表的所有节点组成的。
     * 
     * 示例：
     * 输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4
     * 
     * @param l1
     * @param l2
     * @return
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode headNode = new ListNode(0);
        ListNode curLeft = l1;
        ListNode curRight = l2;
        ListNode curNode = headNode;
        while (curLeft != null || curRight != null) {
            while (curLeft != null
                    && (curRight == null || curLeft.val <= curRight.val)) {
                curNode.next = curLeft;
                curNode = curLeft;
                curLeft = curLeft.next;
            }
            while (curRight != null
                    && (curLeft == null || curRight.val <= curLeft.val)) {
                curNode.next = curRight;
                curNode = curRight;
                curRight = curRight.next;
            }
        }
        return headNode.next;
    }
    
    /**
     * 2. 两数相加
     * 
     * 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
     * 
     * 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
     * 
     * 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
     * 
     * 示例：
     * 
     * 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
     * 输出：7 -> 0 -> 8
     * 原因：342 + 465 = 807
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0); // 待返回的链表的哨兵结点
        ListNode cur = head;
        ListNode cur1 = l1;
        ListNode cur2 = l2;
        int carry = 0;
        while (cur1 != null || cur2 != null) {
            int sum = carry;
            if (cur1 != null) {
                sum += cur1.val;
                cur1 = cur1.next;
            }
            if (cur2 != null) {
                sum += cur2.val;
                cur2 = cur2.next;
            }
            cur.next = new ListNode(sum % 10);
            carry = sum / 10;
            cur = cur.next;
        }
        if (carry != 0) {
            cur.next = new ListNode(1);
        }
        return head.next;
    }
    
    /**
     * 61. 旋转链表
     * 
     * 给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
     * 
     * 示例 1:
     * 
     * 输入: 1->2->3->4->5->NULL, k = 2
     * 输出: 4->5->1->2->3->NULL
     * 解释:
     * 向右旋转 1 步: 5->1->2->3->4->NULL
     * 向右旋转 2 步: 4->5->1->2->3->NULL
     * 示例 2:
     * 
     * 输入: 0->1->2->NULL, k = 4
     * 输出: 2->0->1->NULL
     * 解释:
     * 向右旋转 1 步: 2->0->1->NULL
     * 向右旋转 2 步: 1->2->0->NULL
     * 向右旋转 3 步: 0->1->2->NULL
     * 向右旋转 4 步: 2->0->1->NULL
     * @param head
     * @param k
     * @return
     */
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        // 计算链表的长度，找到尾结点
        ListNode cur = head;
        int len = 1;
        while (cur.next != null) {
            cur = cur.next;
            len++;
        }
        ListNode tail = cur;

        k = k % len;
        if (k == 0) {
            return head;
        }
        int i = len - k;
        ListNode rotateHeadPre = head;
        while (i > 1) {
            rotateHeadPre = rotateHeadPre.next;
            i--;
        }
        ListNode rotateHead = rotateHeadPre.next;
        rotateHeadPre.next = null;
        tail.next = head;
        return rotateHead;
    }
}
